# 递归算法
# # 自己的理解就是 递归=规律+终止条件（一般是从最后一位向前开始推算）
# # 第一道练习题
# # 计算一下第i个数是多少，例如1,3,5,7,9,11,13,15的奇数
# # 分析：
# #     规律是: f(n)=f(n-1)+2
# #     终止条件： f(1)=1
# #     f(n)=f(n-1)+2
# #     f(n)=f(n-1)+2=(f(n-2)+2)+2............f(1)+2+2....


def f(n):
    if n == 1:
        return 1
    else:
        return f(n-1)+2


result1 = f(5)
print(result1)

# 第二个题，计算这n个数的前n项的和,1,2,3,4,5,6,7,8,9,20
# 分析：
#     规律: sum(n)=sum(n-1)+n
#     终止条件： sum(1)=1


def suma(n):
    if n == 1:
        return 1
    else:
        return suma(n-1)+n


result2 = suma(9)
print(result2)

# 第三个题，计算这n个数的前n项的和,1,3,5,7,9
# 分析：
#     规律: Bsum(n)=Bsum(n-1)+f(n-1)+2
#     终止条件： Bsum(1)=1


def bsum(n):
    if n == 1:
        return 1
    else:
        return bsum(n-1)+f(n)


result3 = bsum(5)
print(result3)

# 第四个题，求第n个斐波那契数列 1,1,2,3,5,8,13,21
#     分析：
#         规律：f1(n)=f1(n-1)+f1(n-2)
#         终止条件： f1(1)=1
#                  f1(2)=1


def fibonacci(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fibonacci(n-1)+fibonacci(n-2)


result4 = fibonacci(8)
print(result4)

# 第五题，求前n个斐波那契数列的和
#     分析：sumfibonacci(n)=sumfibonacci(n-1)+fibonacci(n)
#     终止：sumfibonacci(1)=1
#          sumfibonacci(2)=1


def sumfibonacci(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return sumfibonacci(n - 1) + fibonacci(n)


result5 = sumfibonacci(5)
print(result5)

# Fibonacci数列是这样定义的：
# F[0] = 0
# F[1] = 1
# for each i ≥ 2: F[i] = F[i-1] + F[i-2]
# 因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, ...，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。
# 输入描述:
# 输入为一个正整数N(1 ≤ N ≤ 1,000,000)
# 输出描述:
# 输出一个最小的步数变为Fibonacci数"


x = input('请输入一个数字')
xx=int(x)
n = 1
while int(x) > fibonacci(n):
     n += 1
result01 = abs(fibonacci(n)-xx)
result02 = abs(fibonacci(n-1)-xx)
if result01 < result02:
    print(result01)
else:
    print(result02)
